/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

#include <stdio.h>
#include <stdlib.h>
#include "common_list.h"

// 归并排序 
struct ListNode *mergeSortList(struct ListNode *head) {
    return head;
}

// insert sort 插入排序，但是时间会超出
struct ListNode* do_insert(struct ListNode *sorted, struct ListNode *node) {
    struct ListNode *tmp = (struct ListNode *)malloc(sizeof(*sorted));
    tmp->next = sorted;

    struct ListNode *cur = tmp;
    struct ListNode *next = tmp->next;
    while (next) {
        if (next->val > node->val) {
            node->next = next;
            cur->next = node;
            return tmp->next;
        }
        cur = cur->next;
        next = next->next;
    }
    cur->next = node;
    node->next = NULL;
    return tmp->next;
}

static struct ListNode* insertSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode *sorted = head;
    struct ListNode *remain = head->next;
    struct ListNode *ptr = remain;

    sorted->next = NULL;
    while(ptr) {
        remain = ptr->next;
        sorted = do_insert(sorted, ptr);
        ptr = remain;
    }
    return sorted;
}

static struct ListNode* sortList(struct ListNode* head) {
#if 1
    return insertSortList(head);
#else
    return mergeSortList(head);
#endif
}

int main() {
    int val[] = {7, 8};

    struct ListNode* head = generate_list_val(sizeof(val) / sizeof(int), val);
    print_list(head);
    printf("\n");
    print_list(sortList(head));
    return 0;
}